﻿using System;

namespace heapsort2
{
	class MainClass
	{
		public static void Main (string[] args)
		{
			Console.WriteLine ("Hello World!");
			int[] array = new int[]{0,76,50,65,49,97,15,38,27};
			HeapSort (array,array.Length-1);
			foreach (int item in array) {
				System.Console.WriteLine (item+" ");
			}
		}

		static void sift(int[] r,int k,int m)
		{
			int i = k;
			int j = 2 * i;
			int temp = r [i];
			while (j <= m) 
			{
				if (j < m && r [j] < r [j + 1])
					j++;
				if (temp < r [j]) {
					r [i] = r [j];
					i = j;
					j = 2 * i;
				} else
					break;
			}
			r [i] = temp;
		}
		static void HeapSort(int[] r,int n)
		{
			int i,temp;
			for (i = n / 2; i >= 1; i--)
				sift (r, i, n);
			for (i = 1; i < n; i++) 
			{
				temp = r [1];
				r [1] = r [n - i + 1];
				r [n - i + 1] = temp;
				sift (r,1,n-i);
			}
		}
	}
}
